home *** CD-ROM | disk | FTP | other *** search
/ MacTech 1 to 12 / MacTech-vol-1-12.toast / Source / MacTech® Magazine / Volume 12 - 1996 / 12.06 Jun 96 / 12.06 Challenge Text next >
Encoding:
Text File  |  1996-05-10  |  4.7 KB  |  74 lines  |  [TEXT/R*ch]
  1. Postman’s Sort
  2. Everyone knows that sorting algorithms require execution time that grows faster
  3. than linearly with the number of input records.  Specifically, sorting N input
  4. records is known to require somewhere between O(Nlog2N) and O(N2) comparisons,
  5. depending on the specific algorithm and whether one is considering average or
  6. worst-case time, right?  Wrong.  Your Challenge is to code a sorting algorithm
  7. that requires time proportional to the number of input records.
  8. The bounds in the previous paragraph apply to sorting algorithms that are based
  9. on pairwise comparison of input keys.  A distribution sort, however, requires no
  10. key comparisons, and has different performance characteristics.  Imagine, for
  11. example, how the post office might sort mail.  Initially, the mail might be
  12. distributed into piles by country.  Each of those piles might be distributed
  13. into other piles by state.  Those piles might be distributed by city, and then
  14. by street, and finally by address.  All of this could be accomplished by making
  15. a sequence of passes through the input without ever comparing the sort keys of
  16. two input records to one another.  This month, you are to implement a
  17. distribution (or “postman’s”) sort algorithm.  The prototype for the code you
  18. should write is:
  19.  
  20. #include <stdio.h>
  21. static pascal OSErr PostmansSort(
  22.     FILE *inFile,                            /* stream containing sort input */
  23.     FILE *outFile,                        /* stream to contain sort output */
  24.     void *privateStorage,            /* preallocated storage for your use */
  25.     size_t storageSize                /* number of bytes of privateStorage */
  26. );
  27.  
  28. The input will consist of records in the following format:
  29.  
  30. [FirstName] <tab> [MiddleName] <tab> LastName <tab> 
  31. StreetAddress <tab> StreetName <tab> 
  32. City <tab> State <tab> [ZipCode] <tab> [Country] <CR>
  33.  
  34. Input records should be read from inFile, sorted, and written to outFile.  Both
  35. the input and output files will be opened and closed for you by the calling
  36. routine.  Records will consist of up to 8 fields, as indicated above, and be
  37. terminated by a carriage return (0x0D). Fields will be separated by tabs (0x09).
  38. The square brackets in the format description are meta-characters indicating
  39. optional fields; the brackets will not be present in the input.  Fields may
  40. contain embedded spaces or special characters (except tabs and returns).
  41. Records are to be sorted into ascending order with Country as the primary sort
  42. key, ZipCode (if present) as the secondary key, then StreetName, StreetAddress,
  43. LastName, FirstName, and finally MiddleName, in that order.  If ZipCode is not
  44. present, then State and City should replace it as the secondary and tertiary
  45. sort keys, respectively; otherwise State and City should be ignored.  Sort order
  46. should be lexicographic except when a field value is purely numeric, and a
  47. purely numeric field should be treated as smaller than a field containing
  48. non-numeric characters.  That is, field values “1”, “2”, “10”, “1B”, “1C”, and
  49. “2A” would sort in the order indicated.  Empty optional fields should be
  50. considered to have the smallest possible value (e.g., records with no Country
  51. should be output before records with a Country value). Your routine should
  52. return zero (noErr) if it completes normally, or a non-zero error code if it is
  53. unable to complete the sort for any reason.
  54. There are no predetermined limits on the number of distinct countries, State,
  55. City, etc. values that might be present in the input.  Your routine will be
  56. provided with storageSize bytes (at least 64KB) of preallocated storage,
  57. initialized to zero by the calling routine, and pointed to by privateStorage. 
  58. You may not allocate any additional memory, although use of small amounts of
  59. static memory is permitted.  If your solution requires additional storage, you
  60. should create and write to temporary disk files.  Adequate disk space is
  61. guaranteed.  In approximately half of the test cases, you will be guaranteed at
  62. least 32 bytes of memory per record, plus 32 bytes for each unique field value. 
  63. Scoring will weight these high-memory cases equally with the cases where less
  64. memory is provided.
  65. This will be a native PowerPC Challenge, scored using the Metrowerks
  66. environment.  Solutions may be coded in C, C++, or Pascal.  If you use a
  67. language other than C, you should ensure that your code can be called from a
  68. test driver written in C.  Most importantly, to be considered correct, your code
  69. must sort the input into the proper order without performing any key comparisons
  70. between input records.  The fastest correct solution will be the winner.
  71. This Challenge is based on a suggestion from Peter Shank, passed on to me by
  72. Mike Scanlin.  Peter forwarded a reference to an article on the subject by
  73. Robert Ramsey, which you can find at http://www.silcom.com/~ramey/article.html. 
  74.